package leetcode_core.leetcode_1;

import org.junit.Test;

public class MinDistance {
    //定义dp函数 dp(i int,j int) int
    //含义是第s1的[i,s1.length()-1]的串变成s2的[j,s2.length()-1]所需要的最小次数
    private String s1;
    private String s2;
    private int[][] m;
    private int dp(int i,int j){
        //base-case:如果i走完了s1,而j还没走完s2,就可以直接返回另一个字符串剩下的长度了
        if(i==-1){
            return j+1;
        }
        if(j==-1){
            return i+1;
        }
        for(int x = 0;x<s1.length();x++){
            for(int y = 0;y<s2.length();y++){
                m[x][y] = -1;
            }
        }
        //做选择
        if(m[i][j]!=-1){
            return m[i][j];
        }
        if(s1.charAt(i) == s2.charAt(j)){
            //直接返回本次计算的结果
            if(m[i][j] == -1){
                m[i][j] = dp(i-1,j-1);
            }
            return m[i][j];
        }
        //否则就做选择
        //我们来看看插入、删除、替换，在dp函数里面是分别是如何表示的
        //我们以下的表示法是基于s1->s2的过程来写的
        //插入:dp(i,j-1)+1:首先+1就代表着要消耗一次修改次数,然后我们来判断指针如何运动,由于是插入的,因此j对应的字符
        //就被对应上了,而i还没有被匹配,因此i不动,j-1
        //删除:dp(i-1,j)+1与插入是同理的,由于是删除s1中的字符,就相当于是j对应的字符还没有被对应上,而i对应的字符被省略,视而不见,因此i-1了
        //替换:dp(i-1,j-1)+1由于是从s1变成s2,因此就是修改s1中的第i位字符,使得与s2中的第j位字符所对应,这时候两位都匹配上了,i-1,j-1
        if(m[i][j] == -1){
            m[i][j] = Math.min(Math.min(dp(i-1,j)+1,dp(i,j-1)+1),dp(i-1,j-1)+1);
        }
        return m[i][j];
    }

    public int minDistance(String s1,String s2){
        this.s1 = s1;
        this.s2 = s2;
        m = new int[s1.length()+5][s2.length()+5];
        //算法起点是字符串的最末尾
        return dp(s1.length()-1,s2.length()-1);
    }

    @Test
    public void test(){
        System.out.println(minDistance("horse","ros"));
    }


}
